// -*- coding: utf-8 -*- 
/**
 * Project: LanQiao
 * Creator: yanking
 * Create time: 2022-02-20 16:00
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package HuffmanTree;

import java.util.Arrays;
import java.util.Scanner;

public class HuffmanTree {
    // 初始化数组，并且计算对该数组构造霍夫曼树的费用
    public int[] node, merge;
    public int n;
    public int cost = 0;
    public int merNum = 0;


    public void initArray() {
        Scanner myScanner = new Scanner(System.in);
        System.out.println("Input the Array Size");
        n = myScanner.nextInt();
        node = new int[n];
        merge = new int[n / 2];
        for (int i = 0; i < n; i++) {
            node[i] = myScanner.nextInt();
        }
        System.out.println(constructHuffman(node));
    }

    /**
     * to construct the HuffmanTree and  return the cost
     *
     * @param node
     * @return
     */
    public int constructHuffman(int[] node) {
        // 暴力解法
        int i = 0;
        Arrays.sort(node);
        while (i < n - 1) {
            int tmp = node[i] + node[++i];
            cost += tmp;
            node[i] = tmp;
            Arrays.sort(node, i, n);
        }
        return cost;
    }
}


